L2-012 关于堆的判断

题目 L2-012 关于堆的判断

思路分析

y总有讲过手写堆 向上调整向下调整……

但是考察的很少 堆方面就这一题 没什么必要花太多时间复习堆

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};
const int inf = 0x3f3f3f3f;
priority_queue<int> pq;
multiset<int> s;

vector<int> heap(1);

void up(int i) {
    while (i > 1 && heap[i] < heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

void insert(int x) {
    heap.push_back(x);
    up(heap.size() - 1);
}

int findIndex(int x) {
    for (int i = 1; i < heap.size(); ++i)
        if (heap[i] == x)
            return i;
    return -1;
}

void judgeRoot(int x) {
    cout << (heap[1] == x ? "T" : "F") << endl;
}

void judgeSiblings(int x, int y) {
    int ix = findIndex(x), iy = findIndex(y);
    if (ix > iy) swap(ix, iy);
    if (ix % 2 == 0 && iy == ix + 1) cout << "T" << endl;
    else cout << "F" << endl;
}

void judgeParent(int x, int y) {
    int ip = findIndex(x), ic = findIndex(y);
    cout << ((ip * 2 == ic || ip * 2 + 1 == ic) ? "T" : "F") << endl;
}

void judgeChild(int x, int y) {
    int ic = findIndex(x), ip = findIndex(y);
    cout << ((ip * 2 == ic || ip * 2 + 1 == ic) ? "T" : "F") << endl;
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int x; cin >> x;
        insert(x);
    }

    cin.ignore();
    while (M--) {
        string line;
        getline(cin, line);
        int a, b;
        if (line.find("and") != string::npos) {
            sscanf(line.c_str(), "%d and %d", &a, &b);
            judgeSiblings(a, b);
        } else if (line.find("is the root") != string::npos) {
            sscanf(line.c_str(), "%d is the root", &a);
            judgeRoot(a);
        } else if (line.find("is the parent of") != string::npos) {
            sscanf(line.c_str(), "%d is the parent of %d", &a, &b);
            judgeParent(a, b);
        } else if (line.find("is a child of") != string::npos) {
            sscanf(line.c_str(), "%d is a child of %d", &a, &b);
            judgeChild(a, b);
        }
    }
    return 0;
}

同类题型

视频讲解

⬅️ L2-011 玩转二叉树 🏠 00-天梯赛 ➡️ L2-013 红色警报